perm filename TAK.TIM[TIM,LSP]20 blob
sn#738478 filedate 1984-01-12 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00032 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00005 00002 Takeuchi function of various types
C00016 00003 ∂09-Dec-81 0453 Griss at UTAH-20 (Martin.Griss) TAK
C00018 00004 ∂14-Nov-81 0857 Daniel L. Weinreb <dlw at MIT-AI>
C00022 00005 ∂11-Dec-81 1126 Griss at UTAH-20 (Martin.Griss)
C00046 00006 MacLisp produced LAP
C00048 00007 ∂26-Feb-81 2227 CSVAX.fateman at Berkeley
C00050 00008 ∂22-Jan-82 1656 Griss at UTAH-20 (Martin.Griss) Latest V2 VAx times
C00052 00009 ∂23-Jan-82 0931 Griss at UTAH-20 (Martin.Griss) Rep to george
C00059 00010 ∂21-Feb-82 1233 George J. Carrette <GJC at MIT-MC>
C00062 00011 ∂21-Feb-82 2132 Kim.fateman at Berkeley (tak 18. 12. 6.)
C00063 00012 ∂21-Feb-82 2134 ARPAVAX.fateman at Berkeley oops
C00064 00013 ∂21-Feb-82 2134 CSVAX.fateman at Berkeley explanation for the different times....
C00065 00014 ∂21-Feb-82 2139 Kim.fateman at Berkeley more on (tak 18 12 6)
C00067 00015 ∂22-Feb-82 0205 George J. Carrette <GJC at MIT-MC> Timing results.
C00070 00016 ∂23-Feb-82 0234 Kim.fateman at Berkeley gack, another data-point on TAK
C00072 00017 ∂23-Feb-82 1455 Kim.fateman at Berkeley translink etc
C00075 00018 ∂08-Feb-82 1947 Griss at UTAH-20 (Martin.Griss) Progress
C00078 00019 ∂03-Mar-82 2021 George J. Carrette <GJC at MIT-MC> ∂03-Mar-82 1043 George J. Carrette <GJC at MIT-MC>
C00084 00020 ∂26-Apr-82 0053 Kim.jkf at Berkeley franz tak benchmarks
C00089 00021 ∂26-Apr-82 0908 Kim.jkf at Berkeley more on tak
C00093 00022 ELISP/UCILISP
C00094 00023 ∂21-May-82 2048 Martin.Griss <Griss at UTAH-20> Latest PSL Tak times
C00096 00024 LM-2 HIC
C00097 00025 LM-2 HIC
C00098 00026 InterLisp-10
C00099 00027 TAK
C00100 00028 TAK
C00101 00029 SAIL (model B)
C00103 00030 NIL
C00104 00031 SCORE OCT 18, 1983 interlisp
C00105 00032 PSL SCORE 1/10/84 TAK LOCAL!
C00106 ENDMK
C⊗;
Takeuchi function of various types
tak (18. 12. 6.)
On 11/750 in Franz generic arith (sfc)47.6 seconds compiled (JKF time 4/26)
On 11/780 in Franz generic arith (sfc)27.6 seconds compiled (JKF time 4/26)
On 11/750 in Franz ordinary arith 19.9 seconds compiled
On 11/780 in Franz with (sfc)(TAKF) 15.8 seconds compiled (GJC time)
On 11/750 in Franz fixnum arith (sfc) 14.1 seconds compiled (JKF time 4/26)
On 2060 in InterLisp (rc/swl) 13.288 seconds compiled (rpg 8/12)
On 2060 in InterLisp (rc/swl) 12.7 seconds compiled (LM 5/7)
On 11/750 in Franz generic arith (nfc)11.6 seconds compiled (JKF time 4/26)
On Dolphin in InterLisp Nov 1981 (tr) 11.195 seconds compiled
On 11/780 in Franz (sfc) 8.4 seconds compiled (KIM time)
On 11/780 in Franz fixnum arith (sfc) 8.1 seconds compiled (JKF time 4/26)
On 11/780 in Franz (sfc) 8.35 seconds compiled (GJC time)
On 11/780 in Franz generic arith (nfc) 7.7 seconds compiled (JKF time 4/26)
On 11/780 in Franz with (nfc)(TAKF) 7.5 seconds compiled (GJC time)
On 11/750 in PSL, generic arith 7.1 seconds compiled
On 11/750 in Franz (TAKF) 6.7 seconds compiled (JKF time 4/26)
On MC (KL) in MacLisp (TAKF) 5.9 seconds compiled (GJC time)
On Dolphin May 1982 generic arith 5.74 seconds compiled (LM 5/6)
On Dolphin in InterLisp Jan 1982 (tr) 5.71 seconds compiled
On Dolphin May 1982 Inum arith (tr) 5.28 seconds compiled (LM 5/6)
On Dolphin May 1982 generic arith (tr) 5.23 seconds compiled (LM 5/6)
On 2060 in T/UCILISP (sfc) 4.801 seconds compiled (Tyson 5/5)
On 2060 in InterLisp (rc/nsw) 4.57 seconds compiled (LM 5/7)
On Symbolics LM-2 4.446 seconds compiled (HIC)
On 11/780 in Franz (TAKF) 4.3 seconds compiled (JKF time 4/26)
On 11/780 in InterLisp (load = 0) 4.24 seconds compiled
On Dolphin May 1982 gen arth (d/o) 4.21 seconds compiled (LM 5/6)
On 780 in NIL Aug 1983 4.16 seconds compiled
On Foonly F2 in MacLisp 4.1 seconds compiled
On Dolphin May 1982 Inum arth (d/o,tr) 3.88 seconds compiled (LM 5/6)
On Dolphin May 1982 gen arth (d/o,tr) 3.84 seconds compiled (LM 5/6)
On Apollo (MC68000) PASCAL 3.8 seconds (extra waits?)
On 11/750 in Franz, Fixnum arith 3.6 seconds compiled
On MIT CADR in ZetaLisp 3.16 seconds compiled (GJC time)
On 2060 in R/UCILISP (sfc) 3.157 seconds compiled (Hedrick 5/4)
On MIT CADR in ZetaLisp 3.1 seconds compiled (ROD time)
On MIT CADR in ZetaLisp (TAKF) 3.1 seconds compiled (GJC time)
On Symbolics LM-2 2.905 seconds compiled (HIC)
On Apollo (MC68000) PSL SYSLISP 2.93 seconds compiled
On 11/780 in NIL (TAKF) 2.8 seconds compiled (GJC time)
On 11/780 in NIL 2.7 seconds compiled (GJC time)
On 11/750 in C 2.4 seconds
On 11/780 in Franz (nfc) 2.13 seconds compiled (KIM time)
On 11/780 (Diablo) in Franz (nfc) 2.1 seconds compiled (VRP time)
On 11/780 in Franz (nfc) 2.1 seconds compiled (GJC time)
On 11/780 in Franz fixnum arith (nfc) 2.1 seconds compiled (JKF time 4/26)
On 2060 in InterLisp (bc) 2.153 seconds compiled (rpg 8/12)
On 2060 in InterLisp (bc) 2.04 seconds compiled (LM 5/7)
On 68000 in C 1.9 seconds
On 11/750 in Franz fixnum arith (lfc) 1.9 seconds compiled (JKF time 4/26)
On Apollo PSL (10Mz/1Mb/Cache) 1.679 seconds compiled
On Utah-20 in PSL Generic arith 1.672 seconds compiled
On 11/750 in PSL INUM arith 1.4 seconds compiled
On 11/780 (Diablo) in C 1.35 seconds
On 11/780 in Franz (lfc) 1.13 seconds compiled (KIM time)
On UTAH-20 in Lisp 1.6 1.1 seconds compiled
On 11/780 in Franz fixnum arith (lfc) 1.1 seconds compiled (JKF time 4/26)
On UTAH-20 in PSL Inum arith 1.077 seconds compiled
On 2060 in Elisp (nfc) 1.063 seconds compiled (Hedrick 5/4)
On 2060 in R/UCILISP (nfc) .969 seconds compiled (Hedrick 5/4)
On 2060 in T/UCILISP (nfc) .930 seconds compiled (tyson 5/5)
On SAIL (KL) in MacLisp .832 seconds compiled
On SAIL in bummed MacLisp .795 seconds compiled
On MC (KL) in MacLisp (TAKF,dcl) .789 seconds compiled
On 68000 in machine language .7 seconds
On MC (KL) in MacLisp (dcl) .677 seconds compiled
On Symbolics 3600 (no-peep,no-ifp) .633 seconds compiled (PAM 1/7/83 V222)
On SAIL in bummed MacLisp (dcl) .616 seconds compiled
On Symbolics 3600 (peep,no-ifp) .590 seconds compiled (PAM 3/10/83 V222)
On S-1 Mark IIA (Common Lisp) .584 seconds compiled (rpg 11/16/83)
On SAIL (KL) in MacLisp (dcl) .564 seconds compiled
On Dorado in InterLisp Feb 1983 (tr) .526 seconds compiled
On UTAH-20 in SYSLISP arith .526 seconds compiled
On SAIL (KLB) in MacLisp(dcl) .489 seconds compiled
On S-1 Mark IIA (Common Lisp) .410 seconds compiled (rpg 12/02/83)
On S-1 Mark IIA (Common Lisp) .320 seconds compiled (rpg 12/05/83)
On SAIL in machine language .255 seconds (wholine)
On SAIL in machine language .184 seconds (ebox-does not include mem)
On SCORE (2060) in machine language .162 seconds (ebox)
On S-1 Mark I in machine language .114 seconds (ebox & ibox)
On Cray-1, PSL .048 seconds compiled
63609 function calls
max recursion depth is 18
average recursion depth is 15.4
(defun tak (x y z)
(cond ((not (< y x))
z)
(t (tak (tak (1- x) y z)
(tak (1- y) z x)
(tak (1- z) x y))))))
notes:
(tr) means Tail Recursion Removal
(d/o) means Display turned Off on Dolphin
(sfc) means `slow function call' in Franz (debugging setting (like (NOUUO t)))
(nfc) means `normal function call' in Franz (non-debugging setting (like (NOUUO ()))
(lfc) means `local function call' in Franz (function call directly to an entry point
using knowledge of the internals of the
function by the compiler)
(bc) means Block Compiled in InterLisp
(rc) means Regular Compiled in InterLisp
(swl) means SWapping space size set low in InterLisp
(nsw) means No SWapping space in InterLisp
(dcl) means heavy MacLisp declarations
;;; Here are the definitions of TAKF as provided by GJC. #-NIL means
;;; except in NIL, #+NIL means for NIL.
(defun takf (x y z)
(takfsub #'takfsub x y z))
#-NIL
(defun takfsub (f x y z)
(if (not (< y x))
z
(funcall f f (funcall f f (1- x) y z)
(funcall f f (1- y) z x)
(funcall f f (1- z) x y))))
#+NIL
(defun takfsub ((&function f) x y z)
;; lexical scoping of function bindings allows this.
(if (not (< y x))
z
(f #'f (f #'f (1- x) y z)
(f #'f (1- y) z x)
(f #'f (1- z) x y))))
∂09-Dec-81 0453 Griss at UTAH-20 (Martin.Griss) TAK
Date: 9 Dec 1981 0552-MST
From: Griss at UTAH-20 (Martin.Griss)
Subject: TAK
To: RPG at SU-AI
cc: griss at UTAH-20
JUST TO CONFIRM, (TAK 18 12 6), right?
I find times ranging form 0.55 sec to 3.5 sec depending on what sort of arith I
use: 0.55 is SYSLISP arith (unbox on entry, do opencoded arith), to full geeneric
arith.
On old LISP 1.6 system, we get about 1 sec, no fast arith.
I may try to make some macros for fast (Inum ?) arith; pretty easy,
simply define as sequence like:
(DM + (X)
`(BOX (WPLUS2 (UNBOX ,(CADR X)) (UNBOX ,(CADDR X)))))
where I just have to decide how cavalier I want to be about BOX and UNBOX,
ie INUM only, FIXNUMS too, With/without inline tag test...
What times do you find for (TAK 18 12 6), with some of these considerations.
Ill look at some code listing, FTP later today.
-------
Yes. (TAK 18. 12. 6.). Can you get an accurate number for Lisp 1.6?
Also, I'd like to look at the output of the compiler on this.
Thanks.
∂14-Nov-81 0857 Daniel L. Weinreb <dlw at MIT-AI>
Date: 14 November 1981 11:45-EST
From: Daniel L. Weinreb <dlw at MIT-AI>
To: RPG at SU-AI
Regarding the Takeuchi benchmark results:
The figure for "On the Dolphin" does not mean much if you don't say
which version of the software you were using. Masinter has been working
on performance improvements to the subroutine calling lately, and if you
don't make it clear whether your figure predates or postdates his work,
it is impossible to interpret it.
You might be interested to note that the Interlisp-D compiler, used on
the Dolphin, does a recursion removal on this function, doing the final
(tail-recursive outer) call to "tak" with a goto.
People in general seem to think that this is a worthless benchmark
because it is so small and tests such a small and specific set of
features, although I think that it is still worth something despite that
fact.
Masinter thinks that the only benchmarks that are worth considering are
wall-clock times. He has a benchmark of the KLONE system, showing its
wall-clock times on the Dolphin, and on a 20 (or KL-10?) under various
different load levels (measured in TOPS-20 "load average" units). His
figures show that the Dolphin equals a 20 (KL-10? I can't remember)
under a load average of 1.5. (He also shows the measured runtimes for
the 20, which are quite a bit lower than the wall-clock times even for
an unloaded 20). I think Masinter has a good point here, and I think
that this benchmark, both because of the method of timing and because it
is a real,large program is a much more significant benchmark than
anything else I have seen. That is, if I were evaluating machines, it
would impress me a lot more than values of measured runtime for "tak".
BAK is going to work on bringing up a large real Interlisp program for
ISI on Lisp Machines. Maybe we can use this to create similar
benchmarks for LM-2's. I'm not sure it can, because I think maybe the
thing BAK is converting is not a standalone application but rather is a
programming system that extendes other programs. I'll try to ask him
about it.
-- Dan
∂11-Dec-81 1126 Griss at UTAH-20 (Martin.Griss)
Date: 11 Dec 1981 1223-MST
From: Griss at UTAH-20 (Martin.Griss)
To: RPG at SU-AI
cc: Griss at UTAH-20
In-Reply-To: Your message of 11-Dec-81 1212-MST
And here is 1.6 speed, using our compiler, no fast-arith
(maybe can do with Fast ARith, If I can find the apckage):
[PHOTO: Recording initiated Wed 9-Dec-81 5:25AM]
LINK FROM GRISS, TTY 15
TOPS-20 Command processor 4(714)-2
End of COMAND.CMD.8
@<pslλ$Jλ$Jλ$Jlanguages>rlisp
[Keeping]
REDUCE 2 (University of Utah, Nov-23-81) [RLISP] ...
on 1) comp,plap,pgwd;
NIL
2) copreλ$Jλ$Jλ$Jre 80;
3) in tak16.sl;
(SETQ !*COMP T)
T
(SETQ !*PLAP T)
T
(SETQ !*PGWD T)
T
(de tak (x y z)
(cond ((null (Lessp y x)) z)
(t (tak (tak (sub1 x) y z)
(tak (sub1 y) z x)
(tak (sub1 z) x y)))))
(!*ENTRY TAK EXPR 3)
(!*ALLOC 5)
(!*LBL G0013)
(!*STORE 1 0)
(!*STORE 2 -1)
(!*STORE 3 -2)
(!*LOAD 2 1)
(!*LOAD 1 -1)
(!*LINK LESSP EXPR 2)
(!*JUMPNIL G0014)
(!*LOAD 1 0)
(!*LINK SUB1 EXPR 1)
(!*LOAD 3 -2)
(!*LOAD 2 -1)
(!*LINK TAK EXPR 3)
(!*STORE 1 -3)
(!*LOAD 1 -1)
(!*LINK SUB1 EXPR 1)
(!*LOAD 3 0)
(!*LOAD 2 -2)
(!*LINK TAK EXPR 3)
(!*STORE 1 -4)
(!*LOAD 1 -2)
(!*LINK SUB1 EXPR 1)
(!*LOAD 3 -1)
(!*LOAD 2 0)
(!*LINK TAK EXPR 3)
(!*LOAD 3 1)
(!*LOAD 2 -4)
(!*LOAD 1 -3)
(!*JUMP G0013)
(!*LBL G0014)
(!*LOAD 1 -2)
(!*DEALLOC 5)
(!*EXIT)
(!*ENTRY TAK EXPR 3)
(ADD P (C 0 0 5 5)) 270600000000
(213 P 85 16) 325620000125
G0013
(MOVEM 1 0 P) 202054000000
(MOVEM 2 -1 P) 202114777777
(MOVEM 3 -2 P) 202154777776
(MOVE 2 1) 200100000001
(MOVE 1 -1 P) 200054777777
(CALL 2 (E LESSP)) 34100021172
(JUMPE 1 G0014) 322040000000
(MOVE 1 0 P) 200054000000
(CALL 1 (E SUB1)) 34040016100
(MOVE 3 -2 P) 200154777776
(MOVE 2 -1 P) 200114777777
(CALL 3 (E TAK)) 34140163345
(MOVEM 1 -3 P) 202054777775
(MOVE 1 -1 P) 200054777777
(CALL 1 (E SUB1)) 34040016100
(MOVE 3 0 P) 200154000000
(MOVE 2 -2 P) 200114777776
(CALL 3 (E TAK)) 34140163345
(MOVEM 1 -4 P) 202054777774
(MOVE 1 -2 P) 200054777776
(CALL 1 (E SUB1)) 34040016100
(MOVE 3 -1 P) 200154777777
(MOVE 2 0 P) 200114000000
(CALL 3 (E TAK)) 34140163345
(MOVE 3 1) 200140000001
(MOVE 2 -4 P) 200114777774
(MOVE 1 -3 P) 200054777775
(JRST 0 G0013) 254000433520
G0014
(MOVE 1 -2 P) 200054777776
(SUB P (C 0 0 5 5)) 274600000000
(POPJ P) 263600000000
*** TAK 145230 BASE 33 WORDS 83599 LEFT
(0 0 5 5) 5000005
TAK
(SETQ !*TIME T)
T
TIME: 1878 MS
% Turn on Time loop
% Slow Links
(TAK 1 1 1)
1
TIME: 65 MS
(TAK 18 12 6)
7
TIME: 4977 MS
% fast links
(SETQ !*NOUUO NIL)
NIL
TIME: 66 MS
(TAK 1 1 1)
1
TIME: 54 MS
(TAK 18 12 6)
7
TIME: 1102 MS
NIL
TIME: 62 MS
4) quit;
@pop
[PHOTO: Recording terminated Wed 9-Dec-81 5:26AM]
PS, Cna you send me the S-1 code or some such; maybe we can learn some
new tricks.
-------
∂11-Dec-81 1125 Griss at UTAH-20 (Martin.Griss)
Date: 11 Dec 1981 1222-MST
From: Griss at UTAH-20 (Martin.Griss)
To: RPG at SU-AI
cc: Griss at UTAH-20
In-Reply-To: Your message of 11-Dec-81 1212-MST
Here is TAK.PHT; I would appreciate comments/suggestions on code.
We have been rather pressed for time (me hunting funding etc), so
havent speent the needed hours stdying the code sequences. We want VAX
to stabilize so I can run first PSL class next month; hacking like mad
as PSL manual, uitility modules, editor, emode, windows, packages....
---------------------------------------
[PHOTO: Recording initiated Wed 9-Dec-81 5:43AM]
LINK FROM GRISS, TTY 15
TOPS-20 Command processor 4(714)-2
End of COMAND.CMD.8
@psl:rlisp
[Keeping]
REDUCE 2 (RLisp, 1 December 81) ...
1> % LOAD SOME IMPROVED ARITH
1> IN "ARITH-TEST.RED"$%λ$J
NIL
NIL
NIL
*** (TIMERLOOP): base 562401, length 32
TIMERLOOP
*** (AVG): base 562443, length 14
AVG
*** (TESTLOOP): base 562464, length 15
TESTLOOP
*** (ITESTLOOP): base 562514, length 15
ITESTLOOP
*** (WQUOTE): base 562536, length 6
WQUOTE
FASTPLUS2
FASTTIMES2
FASTDIFFERENCE
FASTADD1
FASTSUB1
FASTZEROP
FASTMINUSP
FASTGREATERP
FASTLESSP
NIL
*** (FASTTESTLOOP): base 562613, length 13
FASTTESTLOOP
NIL
NIL
*** (WTESTLOOP): base 562635, length 12
WTESTLOOP
*** (CALL1): base 562656, length 14
CALL1
*** (CALL2): base 562701, length 14
CALL2
*** (FOO1): base 562717, length 1
FOO1
*** (FOO2): base 562720, length 5
FOO2
NIL
*** (WQUOTE): base 562725, length 6
*** Function `WQUOTE' has been redefined
WQUOTE
*** (IARITHERROR): base 562737, length 4
IARITHERROR
NIL
*** (IPLUS2): base 562746, length 15
IPLUS2
*** (ITIMES2): base 562770, length 14
ITIMES2
*** (IDIFFERENCE): base 563016, length 14
IDIFFERENCE
*** (IADD1): base 563037, length 10
IADD1
*** (ISUB1): base 563051, length 10
ISUB1
*** (IZEROP): base 563066, length 12
IZEROP
*** (IMINUSP): base 563105, length 12
IMINUSP
*** (IGREATERP): base 563124, length 17
IGREATERP
*** (ILESSP): base 563145, length 17
ILESSP
NIL
2> IN "TAK.SL'λ$J";
(SETQ !*COMP T)T
% get compiled and code listing
(SETQ !*PLAP T)T
(SETQ !*PGWD T)T
% Using Generic Arith (we believe slower than should be)
(de tak (x y z)
(cond ((null (Lessp y x)) z)
(t (tak (tak (sub1 x) y z)
(tak (sub1 y) z x)
(tak (sub1 z) x y)))))(!*ENTRY TAK EXPR 3)
(!*ALLOC 5)
(!*LBL G0002)
(!*STORE 1 0)
(!*STORE 2 -1)
(!*STORE 3 -2)
(!*JUMPWLESSP G0004 2 1)
(!*LOAD 1 3)
(!*JUMP G0001)
(!*LBL G0004)
(!*LOAD 1 0)
(!*LINK SUB1 EXPR 1)
(!*LOAD 3 -2)
(!*LOAD 2 -1)
(!*LINK TAK EXPR 3)
(!*STORE 1 -3)
(!*LOAD 1 -1)
(!*LINK SUB1 EXPR 1)
(!*LOAD 3 0)
(!*LOAD 2 -2)
(!*LINK TAK EXPR 3)
(!*STORE 1 -4)
(!*LOAD 1 -2)
(!*LINK SUB1 EXPR 1)
(!*LOAD 3 -1)
(!*LOAD 2 0)
(!*LINK TAK EXPR 3)
(!*LOAD 3 1)
(!*LOAD 2 -4)
(!*LOAD 1 -3)
(!*JUMP G0002)
(!*LBL G0001)
(!*EXIT 5)
(ADJSP ST 5) 105 17 0 00 000005
(MOVEM 1 0 ST) 202 01 0 17 000000
(MOVEM 2 -1 ST) 202 02 0 17 777777
(MOVEM 3 -2 ST) 202 03 0 17 777776
(CAMGE 2 1) 315 02 0 00 000001
(JRST 0 G0004) 254 00 0 00 563200
(MOVE 1 3) 200 01 0 00 000003
(JRST 0 G0001) 254 00 0 00 563225
(MOVE 1 0 ST) 200 01 0 17 000000
(PUSHJ ST (E SUB1)) 260 17 0 00 342453
(MOVE 3 -2 ST) 200 03 0 17 777776
(MOVE 2 -1 ST) 200 02 0 17 777777
(PUSHJ ST (E TAK)) 260 17 0 00 347356
(MOVEM 1 -3 ST) 202 01 0 17 777775
(MOVE 1 -1 ST) 200 01 0 17 777777
(PUSHJ ST (E SUB1)) 260 17 0 00 342453
(MOVE 3 0 ST) 200 03 0 17 000000
(MOVE 2 -2 ST) 200 02 0 17 777776
(PUSHJ ST (E TAK)) 260 17 0 00 347356
(MOVEM 1 -4 ST) 202 01 0 17 777774
(MOVE 1 -2 ST) 200 01 0 17 777776
(PUSHJ ST (E SUB1)) 260 17 0 00 342453
(MOVE 3 -1 ST) 200 03 0 17 777777
(MOVE 2 0 ST) 200 02 0 17 000000
(PUSHJ ST (E TAK)) 260 17 0 00 347356
(MOVE 3 1) 200 03 0 00 000001
(MOVE 2 -4 ST) 200 02 0 17 777774
(MOVE 1 -3 ST) 200 01 0 17 777775
(JRST 0 G0002) 254 00 0 00 563171
(ADJSP ST -5) 105 17 0 00 777773
(POPJ ST 0) 263 17 0 00 000000
*** (TAK): base 563170, length 31
TAK
% Using a "quick and dirty" Inum Only Arith (does do calls and checks
% of range
(de Itak (x y z)
(cond ((null (ILessp y x)) z)
(t (Itak (Itak (Isub1 x) y z)
(Itak (Isub1 y) z x)
(Itak (Isub1 z) x y)))))(!*ENTRY ITAK EXPR 3)
(!*ALLOC 5)
(!*LBL G0002)
(!*STORE 1 0)
(!*STORE 2 -1)
(!*STORE 3 -2)
(!*LOAD 2 1)
(!*LOAD 1 -1)
(!*LINK ILESSP EXPR 2)
(!*JUMPNOTEQ G0004 1 (QUOTE NIL))
(!*LOAD 1 -2)
(!*JUMP G0001)
(!*LBL G0004)
(!*LOAD 1 0)
(!*LINK ISUB1 EXPR 1)
(!*LOAD 3 -2)
(!*LOAD 2 -1)
(!*LINK ITAK EXPR 3)
(!*STORE 1 -3)
(!*LOAD 1 -1)
(!*LINK ISUB1 EXPR 1)
(!*LOAD 3 0)
(!*LOAD 2 -2)
(!*LINK ITAK EXPR 3)
(!*STORE 1 -4)
(!*LOAD 1 -2)
(!*LINK ISUB1 EXPR 1)
(!*LOAD 3 -1)
(!*LOAD 2 0)
(!*LINK ITAK EXPR 3)
(!*LOAD 3 1)
(!*LOAD 2 -4)
(!*LOAD 1 -3)
(!*JUMP G0002)
(!*LBL G0001)
(!*EXIT 5)
(ADJSP ST 5) 105 17 0 00 000005
(MOVEM 1 0 ST) 202 01 0 17 000000
(MOVEM 2 -1 ST) 202 02 0 17 777777
(MOVEM 3 -2 ST) 202 03 0 17 777776
(MOVE 2 1) 200 02 0 00 000001
(MOVE 1 -1 ST) 200 01 0 17 777777
(PUSHJ ST (E ILESSP)) 260 17 0 00 347320
(CAME 1 NIL) 312 01 0 00 000000
(JRST 0 G0004) 254 00 0 00 563244
(MOVE 1 -2 ST) 200 01 0 17 777776
(JRST 0 G0001) 254 00 0 00 563271
(MOVE 1 0 ST) 200 01 0 17 000000
(PUSHJ ST (E ISUB1)) 260 17 0 00 347321
(MOVE 3 -2 ST) 200 03 0 17 777776
(MOVE 2 -1 ST) 200 02 0 17 777777
(PUSHJ ST (E ITAK)) 260 17 0 00 347357
(MOVEM 1 -3 ST) 202 01 0 17 777775
(MOVE 1 -1 ST) 200 01 0 17 777777
(PUSHJ ST (E ISUB1)) 260 17 0 00 347321
(MOVE 3 0 ST) 200 03 0 17 000000
(MOVE 2 -2 ST) 200 02 0 17 777776
(PUSHJ ST (E ITAK)) 260 17 0 00 347357
(MOVEM 1 -4 ST) 202 01 0 17 777774
(MOVE 1 -2 ST) 200 01 0 17 777776
(PUSHJ ST (E ISUB1)) 260 17 0 00 347321
(MOVE 3 -1 ST) 200 03 0 17 777777
(MOVE 2 0 ST) 200 02 0 17 000000
(PUSHJ ST (E ITAK)) 260 17 0 00 347357
(MOVE 3 1) 200 03 0 00 000001
(MOVE 2 -4 ST) 200 02 0 17 777774
(MOVE 1 -3 ST) 200 01 0 17 777775
(JRST 0 G0002) 254 00 0 00 563232
(ADJSP ST -5) 105 17 0 00 777773
(POPJ ST 0) 263 17 0 00 000000
*** (ITAK): base 563231, length 34
ITAK
% "quick and dirty(?)" use of SYSLISP arith, all in line, full
% Fixnum range.
% Could be made into (UNBOX) (Wo ...) (BOX) for "fast-arith"
(dm Wsub1 (X) (LIST 'Wdifference (CADR X) '(WCONST 1)))(!*ENTRY WSUB1 MACRO
1)
(!*ALLOC 0)
(!*LOAD 3 (QUOTE (WCONST 1)))
(!*LOAD 2 (CAR (CDR 1)))
(!*LOAD 1 (QUOTE WDIFFERENCE))
(!*LINKE 0 LIST3 EXPR 3)
(MOVE 3 115245) 200 03 0 00 341055
(MOVE 2 1 1) 200 02 0 01 000001
(MOVE 2 0 2) 200 02 0 02 000000
(MOVE 1 (LAPCONSTANT 0)) 200 01 0 00 563303
(JRST 0 (E LIST3)) 254 00 0 00 342401
:LAPCONSTANT 0: 000 00 0 04 003336
*** (WSUB1): base 563276, length 6
WSUB1
(de Wtak (x y z)
(cond ((null (WLessp y x)) z)
(t (Wtak (Wtak (Wsub1 x) y z)
(Wtak (Wsub1 y) z x)
(Wtak (Wsub1 z) x y)))))(!*ENTRY WTAK EXPR 3)
(!*ALLOC 5)
(!*LBL G0002)
(!*STORE 1 0)
(!*STORE 2 -1)
(!*STORE 3 -2)
(!*JUMPWLESSP G0004 2 1)
(!*LOAD 1 3)
(!*JUMP G0001)
(!*LBL G0004)
(!*LOAD 3 -2)
(!*LOAD 2 -1)
(!*LOAD 1 0)
(!*WPLUS2 1 (WCONST -1))
(!*LINK WTAK EXPR 3)
(!*STORE 1 -3)
(!*LOAD 3 0)
(!*LOAD 2 -2)
(!*LOAD 1 -1)
(!*WPLUS2 1 (WCONST -1))
(!*LINK WTAK EXPR 3)
(!*STORE 1 -4)
(!*LOAD 3 -1)
(!*LOAD 2 0)
(!*LOAD 1 -2)
(!*WPLUS2 1 (WCONST -1))
(!*LINK WTAK EXPR 3)
(!*LOAD 3 1)
(!*LOAD 2 -4)
(!*LOAD 1 -3)
(!*JUMP G0002)
(!*LBL G0001)
(!*EXIT 5)
(ADJSP ST 5) 105 17 0 00 000005
(MOVEM 1 0 ST) 202 01 0 17 000000
(MOVEM 2 -1 ST) 202 02 0 17 777777
(MOVEM 3 -2 ST) 202 03 0 17 777776
(CAMGE 2 1) 315 02 0 00 000001
(JRST 0 G0004) 254 00 0 00 563316
(MOVE 1 3) 200 01 0 00 000003
(JRST 0 G0001) 254 00 0 00 563343
(MOVE 3 -2 ST) 200 03 0 17 777776
(MOVE 2 -1 ST) 200 02 0 17 777777
(MOVE 1 0 ST) 200 01 0 17 000000
(SOJ 1 0) 360 01 0 00 000000
(PUSHJ ST (E WTAK)) 260 17 0 00 347361
(MOVEM 1 -3 ST) 202 01 0 17 777775
(MOVE 3 0 ST) 200 03 0 17 000000
(MOVE 2 -2 ST) 200 02 0 17 777776
(MOVE 1 -1 ST) 200 01 0 17 777777
(SOJ 1 0) 360 01 0 00 000000
(PUSHJ ST (E WTAK)) 260 17 0 00 347361
(MOVEM 1 -4 ST) 202 01 0 17 777774
(MOVE 3 -1 ST) 200 03 0 17 777777
(MOVE 2 0 ST) 200 02 0 17 000000
(MOVE 1 -2 ST) 200 01 0 17 777776
(SOJ 1 0) 360 01 0 00 000000
(PUSHJ ST (E WTAK)) 260 17 0 00 347361
(MOVE 3 1) 200 03 0 00 000001
(MOVE 2 -4 ST) 200 02 0 17 777774
(MOVE 1 -3 ST) 200 01 0 17 777775
(JRST 0 G0002) 254 00 0 00 563307
(ADJSP ST -5) 105 17 0 00 777773
(POPJ ST 0) 263 17 0 00 000000
*** (WTAK): base 563306, length 31
WTAK
(SETQ !*TIME T)T
TIME: 7053 MS
% Turn on Time loop
(TAK 1 1 1)1
TIME: 28 MS
(SYS2INT
(WTAK (INT2SYS 1) (INT2SYS 1) (INT2SYS 1)))1
TIME: 69 MS
(TAK 18 12 6)7
TIME: 1672 MS
(SYS2INT
(WTAK (INT2SYS 18) (INT2SYS 12) (INT2SYS 6)))7
TIME: 526 MS
(ITAK 18 12 6)7
TIME: 1077 MS
NIL
TIME: 36 MS
3> QUIT;
@POP
[PHOTO: Recording terminated Wed 9-Dec-81 5:45AM]
-------
;;; MacLisp produced LAP
(LAP TAK SUBR)
(ARGS TAK (() . 3))
(PUSH P 1)
(PUSH P 2)
(PUSH P 3)
(MOVE 7 0 2)
(CAMGE 7 0 1)
(JRST 0 G0002)
(MOVEI 1 0 3)
(JSP T PDLNMK)
(JRST 0 G0001)
G0002
(MOVE 7 0 1)
(SUBI 7 1)
(PUSH FXP 7)
(MOVEI 1 0 FXP)
(CALL 3 'TAK)
(MOVE 7 @ -1 P)
(SUBI 7 1)
(MOVE 3 -2 P)
(MOVE 2 0 P)
(PUSH P 1)
(PUSH FXP 7)
(MOVEI 1 0 FXP)
(CALL 3 'TAK)
(MOVE 7 @ -1 P)
(SUBI 7 1)
(MOVE 3 -2 P)
(MOVE 2 -3 P)
(PUSH P 1)
(PUSH FXP 7)
(MOVEI 1 0 FXP)
(CALL 3 'TAK)
(MOVEI 3 0 1)
(POP P 2)
(POP P 1)
(CALL 3 'TAK)
(SUB FXP (% 0 0 3 3))
G0001
(SUB P (% 0 0 3 3))
(POPJ P)
()
∂26-Feb-81 2227 CSVAX.fateman at Berkeley
Date: 26 Feb 1981 14:42:52-PST
From: CSVAX.fateman at Berkeley
To: CSVAX.jkf@Berkeley, jlk@mit-mc, lisp-forum@mit-mc, rz@mit-mc
Cc: CSVAX.fateman@Berkeley
←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←
| | UCILISP | INTERLISP | MACLISP |Franz/VAX|
|-------------+---------+-----------+---------+---------|
| Interpreter | 57.0 | 26.0 | 22.8 | 65.0 |
|-------------+---------+-----------+---------+---------|
| Compiler | 2.90 | 15.0 | 0.69 | 1.1 ** |
|-------------+---------+-----------+---------+---------|
Times are for (TAK 4 2 0), where TAK is an interesting function
defined by Mr. Ikuo Takeuchi.
(DEFUN TAK (X Y Z)
(COND ((GREATERP X Y)
(TAK (TAK (SUB1 X) Y Z)
(TAK (SUB1 Y) Z X)
(TAK (SUB1 Z) X Y) ))
(T Y) ))
(**) 5.3 with (1- x) etc [no other declarations, so greaterp is closed comp.]
4.1 with local function declaration (fast subroutine call)
1.1 with > open compiled
times on a VAX 11/780 at Berkeley, Feb. 26, 1981
∂22-Jan-82 1656 Griss at UTAH-20 (Martin.Griss) Latest V2 VAx times
Date: 22 Jan 1982 1751-MST
From: Griss at UTAH-20 (Martin.Griss)
Subject: Latest V2 VAx times
To: rpg at SU-AI
cc: griss at UTAH-20
With a new scheme of VAX tags, and recent compiler/optimizer improvements,
on our 11/750 we find for (TAK 18 12 6) [unlesswe have an error??]
PSL ordinary ("generic") arith 7.1 sec
Franz ordinary arith 19.9 sec
PSL INUM arith 1.4
C 2.4
Franz Fixnum 3.6 sec
I think numbers agree with Diablo times *2/3. We expect better ratio on 11/780,
since registers are faster!
In our V2 VAX model, LISP INUMS are tagged 0 and -1, ie, are signed 32 numbers in
27 bit range, hence are actually SYSLISP numbers, ie this is "our" fixnum mode.
Our 7.1 is so much better than Franz 19.9, since we are in INUM range, no
storage alloc at all.
We are getting better.....
I will bring latest PSL manual for you.
-------
∂23-Jan-82 0931 Griss at UTAH-20 (Martin.Griss) Rep to george
Date: 23 Jan 1982 1027-MST
From: Griss at UTAH-20 (Martin.Griss)
Subject: Rep to george
To: rpg at SU-AI
cc: griss at UTAH-20
I sent following reposnse to Charrette:
[Is the table correctly repseneting what you did with TAK]
George:
We have just gotten our second version of VAX PSL running. It is not fully
checked out (just came up last night). It is complete enough to do some
preliminary timings. As you may recall, V1 VAX PSL was comparable in speed
to Franz LISP on our 11/750 under Unix. We have improved arithmetic and
some code generation for the second build.
V2 PSL has a new tagging scheme that gives 28 bit INUMS; i.e. INUMS are
now the same as SYSLISP-integers in the previous model, so that we won't
need to use SYSLISP level integers as much. The new V2 is roughly twice as
fast as V1, i.e. appears faster than Franz (tests still incomplete, please
don't quote yet).
We redid the (TAK 18 12 6) measurements requested by Dick Gabriel, and here
is a summary:
DEC-20/60:
Ordinary LISP1.6 arith 1.1sec
Ordinary PSL arith 1.67
Inum (fast) PSL arith 1.08
SYSLISP arith .526
C (New Utah PCC Implementaton) .977 [ie SYSLISP faster than C here]
VAX 11/750:
PSL V2, ordinary arith 7.1
PSL V2, Inum arith 1.4 [inum =syslisp on VAX now]
Franz, ordinary arith 19.9
Franz, Fixnum arith 3.6 [using 1+, 1-, * etc in Franz]
C on VAX 2.4
Some reference points from Gabriel:
Dolphin 11.1
MIT CADR 3.1
Franz, Fixnum,11/780 2.1 [Diablo at Stanford]
68000 (C) 1.9
C on 11/780 1.35
SAIL Maclisp .83 ( ~.66 on DEC-20/60?)
SAIL "bummed" MACLISP .80
68000 machine code .7
SAIL machine code .184
SCORE machine code .162
S-1 machine code .114
The best MACLISP and machine code times involved open-coded
FIXNUM arithmetic, hand-unfolding of LISP recursion, and
hand-register allocation. Most of this is one automatically in
the PSL compiler.
Do you have some VAX NIL times for TAK. If you make changes from the
simple
(DEFUN TAK (X Y Z)
(COND ((NULL (lessp Y X)) Z)
(T (TAK (TAK (sub1 X) Y Z)
(TAK (sub1 Y) Z X)
(TAK (sub1 Z) X Y)))))
with "lessp" and "sub1" being different closed or open arithmetics (eg
LESSP, SUB1 or < and 1-), such as special declarations, please send
compilation conditions, declarations , sample of code. I think TAK is a bit
small to be representative, but it does show function call and arithmetic
speed.
@begin(MediumFlame)
By the way, I resent a minor implication of your explanation for the use of
Scheme to Unix for NIL VM: that others may use C, but "at MIT we have do
better/more interesting stuff"; we at UTAH may be "in the boon-docks", but
we "ain't hicks".
Our VM is written in PSL itself, since we believe PSL is good enough for
ALL facets of the work, we dont have to resort to another language.
Our PSL to machine compiler has a conventional LISP->LAP step(3 passes),
[with a very powerful, extensible, table-driven LAP]. The LAP
is then either emitted to a file, assembled and deposited in line
(resident PSL compiler), or passed to a LAP to assembly code translator.
Thus on the VAX we build our VM (kernel) by writing kernel code in PSL,
and compiling to UNIX assembler, on the DEC-20 we produce MIDAS, and
for the 68000 Apollo, we produce ASM.
I realize that PSL is not as grandiose a LISP as NIL, since our goals are
to write and maintain a reasonable LISP for DEC-20, VAX, and 68000 that is
efficient, quick to change and experiment with, powerful enough to be used
for Algebra, Graphics and VLSI research, yet managed by 2-3 g
∂21-Feb-82 1233 George J. Carrette <GJC at MIT-MC>
Date: 21 February 1982 15:33-EST
From: George J. Carrette <GJC at MIT-MC>
To: RPG at SU-AI
I'll run TAK tonight on our 780. I take it you know that there is
an incredible difference between the meaning of a function call in
Franz and the meaning of a function call in NIL. In NIL the linkage
frames are set up such that when an error happens the debugger
sees every function call, every argument to every function, and
every LOCAL variable, using a variable<->program-counter-map
which is generated by the compiler. Even though this provides for
a lot of programmer productivity it doesn't cost much, I have
measured the NIL function call at 12% more costly than Franz "fast-links,"
where the debugging is worse than in compiled maclisp. (You know
how much fun it is to debug compiled maclisp!).
I will also run this:
(defun tak (x y z) (takk #'takk x y z))
(defun takk (f x y z)
(if (not (< y x)) z (funcall f (funcall f (1- x) y x)
(funcall f (1- y) z x)
(funcall f (1- z) x y))))
This is very important, because the speed of your FUNCALL is a main
determinant of the usability of your flavor-system, or generic programming
style.
Is this enough background flaming? Sigh. It would be a great service if
you could figure a way to cast these considerations into something other
than the entrenched flame-mode I've been cast into lately by
the climate-of-the-times as it were.
∂21-Feb-82 2132 Kim.fateman at Berkeley (tak 18. 12. 6.)
Date: 21 Feb 1982 18:36:21-PST
From: Kim.fateman at Berkeley
To: rpg@su-ai
Subject: (tak 18. 12. 6.)
seems to take about 13.3 seconds using Franz opus 38, with tak
compiled as a local function, and 21.3 seconds compiled in the normal
fashion. (Any function can be compiled as a local function, but it
takes more room if a local function must also be callable from interpreted
code.)
Run on a vax 11/780 with a load average of about 2.5.
Tail merging was done by the compiler to eliminate the direct recursion.
∂21-Feb-82 2134 ARPAVAX.fateman at Berkeley oops
Date: 21 Feb 1982 19:49:54-PST
From: ARPAVAX.fateman at Berkeley
To: rpg@su-ai
Subject: oops
Something funny with those last numbers. I ran it again, this
time correctly timing it, (I hope) and I got 1.13 seconds for
local function, 8.4 seconds for normal. This still seems strange,
though.
I also timed interlisp VAX, and got about 4.5 seconds, compiled.
∂21-Feb-82 2134 CSVAX.fateman at Berkeley explanation for the different times....
Date: 21 Feb 1982 20:36:38-PST
From: CSVAX.fateman at Berkeley
To: rpg@su-ai
Subject: explanation for the different times....
(< x y) is not open coded unless the compiler can be sure both
arguments are fixnums. (< in maclisp works by accident on floats,
also). (<& x y) is the right thing to do, where the "&" is from
common lisp.
∂21-Feb-82 2139 Kim.fateman at Berkeley more on (tak 18 12 6)
Date: 21 Feb 1982 21:13:08-PST
From: Kim.fateman at Berkeley
To: rpg@su-ai
Subject: more on (tak 18 12 6)
Cc: Kim.jkf@Berkeley
Franz, interpreted, runs it in 77 seconds, Interlisp VAX interpreted
in 199.5 seconds. The interlisp compiler produces some mysterious
code, but it is clear that it also removes the tail-recursive call.
(It seems that interlisp open-compiles sub1 to a "ROTL". Since
the Franz compiler does not specialize 1- to fixnums (it must run on
bignums, too), it seems interlisp has the benefit of additional
optimization.
I look forward to your list of data points on this timing.
∂22-Feb-82 0205 George J. Carrette <GJC at MIT-MC> Timing results.
Date: 22 February 1982 05:05-EST
From: George J. Carrette <GJC at MIT-MC>
Subject: Timing results.
To: RPG at SU-AI
Here is the results I got when running "GJC;TAK >" on four lisps.
All relevant files are on "MC:GJC;TAK *" If the timings you have
for Lispm and Franz are different then please tell me about it.
---------------------------------------------------------------
| Machine |
Test | |
| Lispm | NIL | Franz D | Franz No D| Maclisp |
---------------------------------------------------------------
TAK←TEST | 3.16 | 2.7 | 8.35 | 2.1 | 0.93 |
---------------------------------------------------------------
TAKF←TEST | 3.10 | 2.8 | 15.8 | 7.5 | 5.9 |
---------------------------------------------------------------
Notes: "Franz D" is Franz with debugging, or (sstatus translink ())
"Franz N" is with without ability to backtrace, or
(sstatus translink t)
Franz and NIL timings run on a VAX-780.
Maclisp timings could be further complicated by looking
at (NOUUO T) and (*RSET ()), not to mention FIXNUM declarations
and SUBRCALL. Maclisp on KL-10.
All times in seconds.
The significance of the TAKF←TEST should be obvious.
∂23-Feb-82 0234 Kim.fateman at Berkeley gack, another data-point on TAK
Date: 22 Feb 1982 19:49:49-PST
From: Kim.fateman at Berkeley
To: rpg@su-ai
Subject: gack, another data-point on TAK
John Foderaro pointed out to me that I was running the timing with
(status translink)= nil , which is the debugging setting. It doesn't
really affect the local function, but it makes a big difference for the
"normal compile" version. It reduces it from about 8 seconds to 2.13 seconds,
which perhaps also gives you an idea of function-linkage overhead if
all calls go through the transfer table.
Thus the "best" time is still about 1.13 seconds (localfunction),
then 2.13 (normal function, translink = t), then the other data
as given. (This is for Franz Lisp, on a vax 11/780.)
Well
I must commend you and GJC for providing good results. Both you,
he, and a third party provided results for Franz that are the same to the
second decimal place. I take this as honesty all around. In any event,
for the record, could you please explain exactly the implementational
difference between TRANSLINK=T, translink=(), and the localfunction compilation?
I know what they are in general terms, but a detailed explanation would
be good. Thanks.
-rpg-
∂23-Feb-82 1455 Kim.fateman at Berkeley translink etc
Date: 23 Feb 1982 14:54:51-PST
From: Kim.fateman at Berkeley
To: rpg@su-ai
Subject: translink etc
Cc: Kim.fateman@Berkeley
Local function compilation is the simplest to explain:
a function invocation can be implemented by a jsb directly to
an entry point, if enough information is known at compile time.
This totally inhibits debugging, generally hides the name of the
local function from functions not compiled "at the same time", and
is very fast. in Franz one does (declare (localf tak)) for example.
translink: The first time a function foo is called,
a reference through a table of transfer vector pairs <name, location> is made,
by jumping to "location" associated with foo. Initially this pair is
<foo, qlinker>
Qlinker is a general calling routine which refers to the atom's (foo's)
function definition cell, accessing its definition. If the definition
is binary code, say bcd←foo then the pair in the transfer table is updated,
if translink = t, to be <foo, bcd←foo>. The function is then invoked.
The next time foo is invoked, the branch to Qlinker is avoided, and it
goes much faster.
If foo is not compiled, or if translink is NIL, then the transfer table
remains unchanged, and the overhead of going through qlinker is present
each time foo is called.
Setting translink to t leaves somewhat less information on the stack, so
the backtrace function has to work harder to find out what happened. Also,
if foo's definition cell is changed, a re-linking has to be done.
There is an analogous kind of thing in interlisp, called linked
and non-linked functions.
∂08-Feb-82 1947 Griss at UTAH-20 (Martin.Griss) Progress
Date: 8 Feb 1982 2043-MST
From: Griss at UTAH-20 (Martin.Griss)
Subject: Progress
To: rpg at SU-AI
cc: griss at UTAH-20
Latest version of VAX PSL now runs all of RLISP, and should have LAP and
compiler by end of week.
I have now (hard weekend!) gotten enough of PSL/SYSLISP compiling to 68000
to have run VERY rough TAK timing on APOLLO:
Recall TAK(18,12,6) was .52 secs on DEC-20; on Apollo is about 2.9 secs.
You had 1.9secs (C) and 0.7 secs (machine code) for 68000. Do you know what
speed (8-10Mz) and what sort of memory delays. Apollo apparently has additional
WAIT states, so I guess PSL probably comparable to C on 68000. Maybe we can get
Brown C up for Apollo or some similar scheme to compare basic times.
Perhaps someone (Pratt) could run me a basic loop, such as counting to N in
D reg, for appropriate large N:
move!.I #100000,D1
L tst D1
JZ done
subq.l #1,D1
jmp L
done exit
or some such, just to normalize speed. Would like copy of EXACT code,
either in C or in ASM(prefarably?)
M
-------
∂10-Feb-82 0542 Griss at UTAH-20 (Martin.Griss)
Date: 10 Feb 1982 0637-MST
From: Griss at UTAH-20 (Martin.Griss)
To: RPG at SU-AI
cc: Griss at UTAH-20
In-Reply-To: Your message of 9-Feb-82 2219-MST
I also have 2.9 secs, on 68000 (apollo, slower than SUN?) in SYSLISP
3.4 secs in Apollo PASCAL
-------
∂10-Feb-82 0542 Griss at UTAH-20 (Martin.Griss)
Date: 10 Feb 1982 0640-MST
From: Griss at UTAH-20 (Martin.Griss)
To: RPG at SU-AI
cc: Griss at UTAH-20
In-Reply-To: Your message of 9-Feb-82 2219-MST
PS, actually, Apollo, 68000 times: 2.93 for PSL/SYSLISP mode
3.80 for PASCAL times.
We need to check basic Apollo vs SUN speeds, I think we extra WAIT states.
-------
∂03-Mar-82 2021 George J. Carrette <GJC at MIT-MC> ∂03-Mar-82 1043 George J. Carrette <GJC at MIT-MC>
Date: 3 March 1982 23:21-EST
From: George J. Carrette <GJC at MIT-MC>
Subject: ∂03-Mar-82 1043 George J. Carrette <GJC at MIT-MC>
To: RPG at SU-AI
Heck, but that so-called BUMBED maclisp was slower than using
a simple fixnum declaration, what gives? Who did that?
(declare (fixnum (tak fixnum fixnum fixnum)
(takf fixnum fixnum fixnum)
(takfsub () fixnum fixnum fixnum)))
(defun tak←test ()
(let ((tt (runtime)))
(declare (fixnum tt))
(tak 18. 12. 6.)
(quotient (- (runtime) tt) 1.0e6)))
(defun tak (x y z)
(if (not (< y x))
z
(tak (tak (1- x) y z)
(tak (1- y) z x)
(tak (1- z) x y))))
(defun takf←test ()
(let ((tt (runtime)))
(declare (fixnum tt))
(takf 18. 12. 6.)
(quotient (- (runtime) tt) 1.0e6)))
(defun takf (x y z)
(takfsub (get 'takfsub 'subr) x y z))
(defun takfsub (f x y z)
(if (not (< y x))
z
(subrcall fixnum f f (subrcall fixnum f f (1- x) y z)
(subrcall fixnum f f (1- y) z x)
(subrcall fixnum f f (1- z) x y))))
Let me put this another way. None of the MacLisp timings on SAIL used
any declarations aside from the implicit ones in the < and 1- operators.
The ``Bummed'' MacLisp means exactly this: It is the MacLisp code that
most directly corresponds to the ``bummed'' assembly language on the
10. Here is that code. The idea is that the bottom-most leaves of the
evaluation tree are trimmed. The BTAK is tail recursive too, which makes it
faster (in the presence of equally missing declarations) than the
normal version.
tak1 caig a,(b) ;x < y quit
popj p,
tak2 add fxp,[5,,5] ;allocate 5 slots. 3 for args, 2 for temporaries
dmovem a,-2(fxp) ;move a,b,c onto the stack. add is used to push
movem c.(fxp) ;empty space, and the assumption of a large enough
;stack is used here. PUSH, ADJSP both do bounds
;checking. DMOVEM saves an instruction fetch and a
;decode.
movei a,-1(a) ;a←a-1 using the address hardware. Assumption
;is that 18 bit, non-negative arithmetic is going on
caile a,(b) ;early quit? c already contains the right result.
;this early quit just unwinds the first arm of
;the conditional. Tak2 is the entry after that arm
pushj p,tak2 ;no go on
movem c,-4(fxp) ;save result on fxp
dmove a,-1(fxp) ;get y,z
move c,-2(fxp) ;and x
movei a,-1(a) ;sub1
caile a,(b) ;early quit
pushj p,tak2
movem c,-3(fxp) ;stash result
move a,(fxp) ;z
dmove b,-2(fxp) ;x,y
movei a,-1(a) ;sub1
caile a,(b)
pushj p,tak2
dmove a,-4(fxp) ;get first 2 results, the last already in c
;notice how the choice of c as the results
;register allowed us to hack the dmove's here
sub fxp,[5,,5] ;flush temporary space
caig a,(b) ;early quit on tail recursion?
popj p, ;qed
jrst tak2 ;tail recursion
It is interesting, though, that the `bummed' version improves less with
declarations than the unbummed one. The point of this study is to try to
understand what every little change to the code does in terms of
performance relative to each other, not to `do the best' in all cases.
In any event, your comments are well taken and are being incorporated
into the record of this research. If you have any other benchmarks, let
me know. Thanks.
-rpg-
∂26-Apr-82 0053 Kim.jkf at Berkeley franz tak benchmarks
Date: 26 Apr 1982 00:40:32-PDT
From: Kim.jkf at Berkeley
To: rpg@su-ai
Subject: franz tak benchmarks
Cc: Kim.fateman@Berkeley, Kim.jkf@Berkeley
There seems to be a misunderstanding about the possible function linkages
in Franz Lisp. Your report lists, 'normal function call',
and 'fast function call'. Franz lisp users would call these 'slow
function call' and 'normal function call'. There are modes which
are even slower than 'slow function call'. You can (*rset t) and
get 'real slow function call' or bind evalhook and get
'real real slow function call'. From experience I can say that the
normal mode for franz users with compiled code is to set the
linkages on (what your report called 'fast function call'). Since
I believe the purpose of the lisp timing project was to compare lisps
as they are typically run, I hope that you use our 'linkages on' numbers
for comparison with other systems.
Your note about 'local function call' is also wrong. A function
declared local is not examined by the compiler in any greater detail
than any other function. The only requirement is that a function declared
local actually appear in the same file and that it not be a lexpr.
I re-ran all timings you requested tonight. The lisp system and
compiler which produced these timings is available to anyone who
asks for it. The source is sitting on our c70 arpanet host.
I want to thank you for taking time to organize the collection of
timing information. I find the results very interesting.
Tak benchmarks run 26 april 82 by jkf
Lisp Opus 38.13, Liszt 8.05
(cpu time in secs, no gc's occurred)
Link type 780 750
--------- ------ ------
generic slow 28.6 51.0
arithmetic normal 7.8 11.6
fixnum slow 8.3 14.8
arithmetic normal 2.1 3.3
local function n/a 1.1 1.9
calls
------
takf n/a 4.3 6.7
(with funcalls)
Key: slow = (sstatus translink nil), fasl = (sstatus translink on)
n/a = doesn't make any difference how the links are set.
The generic example uses add1, sub1, lessp. All others use the
fixnum specific operations.
takf uses funcall rather than the normal way of function calling.
Franz
Your note was well taken. I have updated my notes accordingly. Could you
please explain in more detail what the local function call accomplishes?
Perhaps a quick description of the runtime stack and some code comparing the
results of normal function call and local function call would help me
understand (and explain it to others) what's up. Thanks.
Also I will include your new benchmark in the crop.
-rpg-
∂26-Apr-82 0908 Kim.jkf at Berkeley more on tak
Date: 26 Apr 1982 08:56:02-PDT
From: Kim.jkf at Berkeley
To: rpg@su-ai
Subject: more on tak
Cc: Kim.fateman@Berkeley
I forgot to mention that our compiler does tail recursion removal.
This applies to all tak's except takf.
I don't know if it is too late to submit a function for benchmarking,
but I'll try anyway. The tak function does test function calling speed,
an important part of any lisp system. It also tests the compilation
of 1-, which is far less important. I've rewritten tak to test another
important part of a lisp system: the speed at which it cdr's down
a list. Here is takl:
;;--- takl : tak using lists as counters
;
(defun takl (x y z)
(cond ((listgeqp y x) z)
(t (takl (takl (cdr x) y z)
(takl (cdr y) z x)
(takl (cdr z) x y)))))
;--- listgeqp : t iff list a is longer or the same size as b
;
(defun listgeqp (a b)
(cond ((null b) t)
((null a) nil)
(t (listgeqp (cdr a) (cdr b)))))
I re-ran all benchmarks this morning on less loaded machines and
here are the results:
Tak benchmarks run 27 april 82 by jkf
Lisp Opus 38.13, Liszt 8.05
(cpu time in secs, no gc's occurred)
Link type 780 750
--------- ------ ------
generic slow 27.6 47.6
arithmetic normal 7.7 11.6
fixnum slow 8.1 14.1
arithmetic normal 2.1 3.3
local function n/a 1.1 1.9
calls
------
takf n/a 4.3 6.7
(with funcalls)
------
takl slow 23.1 39.3
(with lists) normal 9.0 14.2
takl 6.4 10.5
(local functions)
Key: slow = (sstatus translink nil), fasl = (sstatus translink on)
n/a = doesn't make any difference how the links are set.
The generic example uses add1, sub1, lessp. All others use the
fixnum specific operations.
takf uses funcall rather than the normal way of function calling.
;;; ELISP/UCILISP
In Elisp, all final calls are turned into jumps. A tailrecursive
function does in fact turn into a loop. I think the R/UCI compiler does
the same, but I am not as familiar with at. (As you may know, the Elisp
compiler is a modified Utah PSL compiler from about a year ago.)
Elisp
(tak 18 12 6) 1.063 (0)
(takf 18 12 6) 2.094 (0)
R/UCI Lisp, NOUUO
(tak 18 12 6) .969 (0)
(takf 18 12 6) 3.157 (0)
-------
∂21-May-82 2048 Martin.Griss <Griss at UTAH-20> Latest PSL Tak times
Date: 21 May 1982 2115-MDT
From: Martin.Griss <Griss at UTAH-20>
Subject: Latest PSL Tak times
To: rpg at SU-AI
cc: griss at UTAH-20
We are now running V3 PSL on all machines (20, VAX and Apollo).
I attach following tiomes, tho am suprized that ARITH time went up.
May indicate other opts slipped in recent builds.
Latest PSL Times for TAK (the older JMC TAK)
As of 9:08pm Friday, 21 May 1982
Note that in V3 PSL, we have new tagging scheme (0 for POSINT, -1 for
NEGINT, so INUM times replace==are SYSLISP times]
For some reason, Generic ARITH times went up (?) will check.
Utah-20: PSL (TAKF, Inum) 443 ms
PSL (generic arith) 1936 ms [Was 1.672, need test INUM first?]
Fast Link LISP 1.6 990 ms
VAX-11/750:
PSL (TAKF,Inum) 1292 ms
PSL (generic) 7344 ms
Apollo/Domain
PSL (TAKF, Inum) 2932 ms
-------
LM-2 HIC
;; 2. TAK
(DEFUN TEST-TAK ()
(TIMING "TAK" (TAK 18. 12. 6.)))
;; Compiled: 2.905 seconds
;; Interpreted: 291 seconds
LM-2 HIC
;; 4A. TAKF (????)
;; Where did this come from?
(DEFUN TEST-TAKF ()
(TIMING "TAKF" (TAKF 18. 12. 6.)))
;; Compiled: 4.446 seconds.
;; Interpreted: long.
InterLisp-10
TAK, normal compiled, Integer arith (swapping space low?)
tak(18,12,6) 13.288
tak(2018,2012,2006) 20.285
Block compiled
tak(18,12,6) 2.1534
tak(2018,2012,2006) 2.47575 and 6.2775 gc seconds (amortized over 4 runs)
RPG and Jim Bennett
;;; TAK
D3
Display-up
Elapsed .564
CPU .564
Display-down
Elapsed .526
CPU .526
;;; TAK
D2
Display-up
Elapsed 5.23
CPU 5.23
Display-down
Elapsed 3.84
CPU 3.84
;;; SAIL (model B)
(fasload tak)
(timit)
Timing performed on Tuesday 06/28/83 at 13:25:15.
Cpu (- GC) Time = 0.49
Elapsed Time = 1.7
Wholine Time = 0.7
GC Time = 0.0
Load Average Before = 1.30323982
Load Average After = 1.32373989
Average Load Average = 1.31348985
NIL
Timing performed on Tuesday 06/28/83 at 13:25:21.
Cpu (- GC) Time = 0.489
Elapsed Time = 2.25
Wholine Time = 0.85
GC Time = 0.0
Load Average Before = 1.37133515
Load Average After = 1.39720452
Average Load Average = 1.38426983
NIL
Timing performed on Tuesday 06/28/83 at 13:25:29.
Cpu (- GC) Time = 0.489
Elapsed Time = 0.85
Wholine Time = 0.81666667
GC Time = 0.0
Load Average Before = 1.3880657
Load Average After = 1.38561296
Average Load Average = 1.38683933
NIL
;;; NIL
TAK
Generic arithmetic (!):
cpu=8.04,elapsed=8.05,pf=0
Number-consing version should be the same:
cpu=8.02,elapsed=8.03,pf=0
Fixnum-only arithmetic (presumably the "real" one):
cpu=4.16,elapsed=4.16,pf=0
;;; SCORE OCT 18, 1983 interlisp
MAKEFILE(TAK)
BCOMPL(TAK)
ST
(TIME (TAK 18 12 6) 1 3)
0 conses
2.089 seconds
0.0 seconds, garbage collection time
7
←
(TIME (TAK 18 12 6) 1 3)
0 conses
2.088 seconds
0.0 seconds, garbage collection time
7
←
;;; PSL SCORE 1/10/84 TAK LOCAL!
(ON TIME)
NIL
Cpu time: 2814 ms
3 lisp> (TIMIT)
NIL
Cpu time: 4662 ms
4 lisp> (TIMIT)
NIL
Cpu time: 4695 ms
5 lisp> (TIMIT)
NIL
Cpu time: 4668 ms
6 lisp>